package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-12 11:48
 **/
public class LeetCode5955 {

    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int dp[] = new int[fruits.length], max = 0;
        for (int i = 0; i < fruits.length; i++) {
            dp[i] = (i > 0 ? dp[i - 1] : 0) + fruits[i][1];
        }
        for (int i = 0, j = i, sum = 0; i < fruits.length; sum -= fruits[i++][1]) {
            while (j < fruits.length
                    && 2 * Math.max(0, startPos - fruits[i][0]) + Math.max(0, fruits[j][0] - startPos) <= k) {
                max = Math.max(max, sum += fruits[j++][1]);
            }
        }
        for (int i = fruits.length - 1, j = i, sum = 0; i >= 0; sum -= fruits[i--][1]) {
            while (j >= 0 && 2 * Math.max(0, fruits[i][0] - startPos) + Math.max(0, startPos - fruits[j][0]) <= k) {
                max = Math.max(max, sum += fruits[j--][1]);
            }
        }


        return max;
    }

}
